UVa/11495 - Bubbles and buckets/11495.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <map>
  19 #include <set>
  20
  21 int numbers[100001];
  22 int a[50005], b[50005];
  23 int n;
  24
  25
  26 /*
  27   Sorts the elements from numbers [start ... end) in decreasing order
  28   and returns the number of inversions in that piece of array.
  29 */
  30 long long merge_sort(int start, int end){
  31   long long cnt = 0;
  32   if (start + 1 == end){ //Single element
  33     return cnt;
  34   }
  35
  36   int m = (start + end)/2;
  37   cnt += merge_sort(start, m) + merge_sort(m, end);
  38
  39   int _a = m - start, _b = end - m;
  40   for (int i=start; i<start+_a; ++i){
  41     a[i-start] = numbers[i];
  42   }
  43
  44   for (int i=m; i<m+_b; ++i){
  45     b[i-m] = numbers[i];
  46   }
  47
  48   for (int i=0, j=0; i<_a && j<_b; ){
  49     if (a[i] > b[j]){
  50       cnt += (long long)(_b - j);
  51       ++i;
  52     }else{
  53       ++j;
  54     }
  55   }
  56
  57   a[_a] = b[_b] = -1;
  58
  59   for (int k=start, i=0, j=0; k<end; ++k){
  60     if (a[i] > b[j]){
  61       numbers[k] = a[i++];
  62     }else{
  63       numbers[k] = b[j++];
  64     }
  65   }
  66
  67   return cnt;
  68 }
  69
  70
  71 int main(){
  72   while (scanf("%d", &n)==1 && n){
  73     for (int i=0; i<n; ++i){
  74       scanf("%d", &numbers[i]);
  75     }
  76
  77     long long cnt = merge_sort(0, n);
  78     //printf("%lld\n", cnt);
  79     puts((cnt % 2 ? "Marcelo" : "Carlos"));
  80   }
  81   return 0;
  82 }
  83
  84